package com.sicheng.蓝桥.练习题;

import org.junit.Test;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/3/28 14:31
 */
public class 快速幂 {
    public static void main(String[] args) {
//        System.out.println(quickMi(2, 100, 3));
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while (t-- > 0) {
            long n = scan.nextLong();
            long m = scan.nextLong();
            long p = scan.nextLong();
            long s1 = System.nanoTime();
            System.out.println(q(n % p, m, p));
            long s2 = System.nanoTime();

            long s3 = System.nanoTime();
            System.out.println(f(n, m, p));
            long s4 = System.nanoTime();

            System.out.println(s2 - s1 + "ns");
            System.out.println(s4 - s3 + "ns");
        }
    }

    //优质算法
    public static long q(long n, long m, long p) {
        long ans = 1;
        while (m > 0) {
            if ((m & 1) == 1) {
                ans = ans * n % p;
            }
            n = n * n % p;
            m >>= 1;
        }
        return ans;
    }

    //性能次之，开辟栈非内存
    public static long f(long n, long m, long p) {
        long temp;
        if (m == 0) {
            return 1;
        } else if (m % 2 == 0) {
            temp = f(n, m / 2, p);
            return temp * temp % p;
        } else {
            temp = f(n, m / 2, p);
            return temp * temp % p * n % p;
        }
    }

    public long mod(long base, long p) {
        for (long i = 1; i < 100; i++) {
            if (Math.pow(base, i) % p == 1) {
                return i;
            }
        }
        return -1;
    }

    public static long quickMi(int a, int b) {

        int ans = 1;
        int base = a;
        while (b > 0) {
            if ((b & 1) != 0)
                ans *= base;
            base *= base;
            b >>= 1;
        }
        return ans;
    }


    @Test
    public void test() {

        // a^(x+y)%p======> a^x % p * a^y % p
        System.out.println(Math.pow(7, 10) % 11);
        // (2^20+ 3^30+4^40+5^50+6^60 )%7 ===== 0
        long mod = mod(2, 7);
        long mod1 = mod(3, 7);
        long mod2 = mod(4, 7);
        long mod3 = mod(5, 7);
        long mod4 = mod(6, 7);
        System.out.println();

    }

    @Test
    public void test1() {
        // 小平方
        int count = 0;
        int n = (int) (1e7 + 3);
        for (int i = 1; i <= n; i++) {
            if (i * i % n * 2 < n) {
                count++;
            }
        }
        System.out.println(count);
    }

    @Test
    public void test2() {
        for (int i = 101; i < 10000; i++) {
            int p = i / 10;
            for (int j = 102; j < 10000; j++) {
                System.out.println((i * j) % p == (i % p) * (j % p));
            }
        }
    }

}
